package algorithm.dynamic_planning.leetcode;

/**
 * dp解决最大子数组和的问题
 * @Author: yuisama
 * @Date: 2022/4/11 18:13
 * @Description:
 */
public class Num53_MaxSubArray {
    // dp
    public int maxSubArray(int[] nums) {
        // dp[] 数组的定义 : 以nums[i]结尾的最大连续子数组和
        // 若dp[i - 1]已知，则以nums[i]结尾的dp[i] = max(nums[i],nums[i] + dp[i - 1])
        int n = nums.length;
        int[] dp = new int[n];
        // 1.base case.数组第一个元素一定是当前最大数组和
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i],nums[i] + dp[i - 1]);
        }
        int res = Integer.MIN_VALUE;
        // 寻找dp数组中最大值
        for (int i = 0; i < n; i++) {
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
